package simulation;

import java.util.ArrayList;
import java.util.List;

/**
 * @Description 剑指 Offer 62. 圆圈中最后剩下的数字
 * @Author Firenut
 * @Date 2023-03-21 21:35
 */
public class T62_lastRemaining {
    /**
     * 法2：在k神的评论区看到一个大佬的回答:（k神的题解讲的有问题，不太理解）
     * 无序列表f(n)的具体含义应该是长度为n的约瑟夫环中最后剩下的数字的原始索引，这个索引随 m(删除第m个数)的改变而改变，换句话说，
     * 只要m不变，这个索引就不会变，而无所谓这个索引对应的数字具体是几，这是能够递推的前提。
     * 无序列表 文中的(m-1)%n 和 m%n 是删除的数字对应的索引 和 下一个开始的数字的索引，而不是数字。
     * 被删除元素的索引: (m-1)%n
     * 新一轮的元素索引: m%n
     * index(n-1): 删除一个元素后 后面元素在新环的索引
     * index(n): 删除一个元素后 后面元素在旧环的索引
     * <p>
     * 删除一个数后在 新约瑟夫环的索引 index(n-1)          要删除的元素索引                      删除一个数后下一轮开始的第一个数在旧环的索引 index(n) [即下一个数的开始索引]
     * 0                         --->    (m-1)%n 即:[0+(m-1)]%n               m%n
     * 1                         --->    (m)%n                              (m+1)%n
     * 2                         --->    (m+1)%n                            (m+2)%n
     * ...                        ...                                  ...
     * n-2                        --->     (m+3)%n                            (m+n-2)%n
     * <p>
     * 由以上得出递推式： index(n-1)  --->     (m-1+index(n-1))%n      index(n) = (m+index(n-1))%n
     * 也就是说，现在的环索引为0 对应原来的索引为3的，换句话说，旧环的索引3跑到新环的索引0位置上了
     * f(n)​ = (f(n−1)+m%n)%n = (f(n−1)+m)%n
     * 也即按照递推式,可以推出 被删一个数后新一轮第一个数在旧环的索引
     * ​  而递推的初始值就是当环的长度为1是,该索引为 0
     */
    public int lastRemaining1(int n, int m) {
        int result = 0;                      // 只有一个数的时候,留下来的肯定是0
        for (int i = 2; i <= n; i++) {       // i表示元素的个数，从2开始
            result = (result + m) % i;       // 注意i一直在变
        }
        return result;
    }


    /**
     * 法1：模拟，选用ArrayList而不是LinkedList，是因为在remove(m)操作的时候，
     * LinkedList需要从头开始遍历，而ArrayList在remove时先通过索引定位到位置 O(1)
     * 然后采用copy的方式将后面的元素前移一个位置，这个效率稍微要比LinkedList好一点
     * 时间复杂度：O(n^2) remove时间复杂度为O(n),需要进行n-1次的元素删除
     */
    public int lastRemaining(int n, int m) {
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            list.add(i);
        }
        int index = (m - 1) % n;
        while (n > 1) {
            list.remove(index);
            n--; // 先-1再取模计算下个索引
            index = (index + m - 1) % n; // index+m-1可能会超过n,所以需要取模
        }
        return list.get(0);
    }
}
